package 算法基础模板.chapter_02;

/**
 * 手写堆
 * <p>
 * 插入一个数 heap[++size] = x; up(size);
 * 求集合中的最小值 heap[1]
 * 删除最小值 heap[1] = heap[size--]; down(1);
 * 删除任意一个元素 heap[k] = heap[size--]; down(k); up(k);
 * 修改任意一个元素 heap[k] = x; down(k); up(k);
 * <p>
 * 完全二叉树, 除了最后一层, 其他层都是非空的, 最后一层从左到右依次排布
 * <p>
 * 小根堆, 根节点小于等于左右两边的最小值
 * 一维数组存储,
 * <p>
 * x的左儿子  2x
 * x的右儿子 2x + 1
 * <p>
 * //
 * //
 *
 * @author Summerday
 */
public class HeapTemplate {

    private final Integer N = 100050;

    int[] h;
    int size;

    // ph[k]存储第k个插入的点在堆中的位置
    int[] ph;

    // hp[k]存储堆中下标是k的点是第几个插入的
    int[] hp;
    int m;


    HeapTemplate (int[] nums) {
        int n = nums.length;
        this.size = 0;
        h = new int[N];
        ph = new int[N];
        hp = new int[N];
        //for (int i = 1; i <= nums.length; i++) {
        //    h[i] = nums[i - 1];
        //}
        //for (int i = nums.length / 2; i > 0; i--) down(i);
        for (int num : nums) insert(num);
    }

    public static void main (String[] args) {

        HeapTemplate template = new HeapTemplate(new int[]{2, 1, 3, 42, 4, 5, 2, 2, 4, 2, 1, 4, 5, 3});

        template.print();

        System.out.println("min of heap : " + template.getMin());

        template.insert(10);
        template.print();

        template.updateK(4, 100);

        template.print();

        template.deleteK(8);

        template.print();


    }

    // 向下调整
    private void down (int u) {
        int t = u;
        if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2; // 判断左儿子是否存在, 且如果左儿子比它小,就更新坐标
        if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; // 同理
        if (u != t) { // 如果需要交换
            heap_swap(u, t);// 交换一下
            down(t); // 继续做这个操作
        }
    }

    // 向上调整
    private void up (int u) {
        while (u / 2 > 0 && h[u / 2] > h[u]) {
            heap_swap(u / 2, u);
            u /= 2;
        }
    }

    // 移除 堆顶
    int removeHead () {
        int ret;
        ret = h[1];
        heap_swap(1, size);
        size--;
        down(1);
        return ret;
    }
    // 获取最小值
    int getMin () {
        return h[1];
    }

    private void swap (int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    // 插入一个数
    void insert (int x) {
        size++;
        m++;
        ph[m] = size;
        hp[size] = m;
        h[size] = x;
        up(size);
    }

    // 删除第k个插入的数
    void deleteK (int k) {
        // ph[k]存储第k个插入的点在堆中的位置
        k = ph[k];
        heap_swap(k, size);
        size--;
        // 下面这俩操作只会执行一次
        down(k);
        up(k);
    }

    // 更新第k个插入的数
    void updateK (int k, int x) {
        k = ph[k];
        h[k] = x;
        down(k);
        up(k);
    }

    void heap_swap (int a, int b) {
        swap(ph, hp[a], hp[b]);
        swap(hp, a, b);
        swap(h, a, b);
    }


    void print () {
        for (int i = 1; i <= size; i++) System.out.print(h[i] + " ");
        System.out.println();
    }
}
